/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 递归，根据新的左子树和右子树
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
    return buildEveryLevel(inorder, postorder)
};

/**
 * 
 * @param {array} inorder 中序树
 * @param {array} postorder 后续树
 * @returns 节点
 */
function buildEveryLevel(inorder, postorder) {
    // 确定终止条件
    if (inorder.length === 0) {
        return null
    }
    // 确定单次递归逻辑：分隔新的中序左子树，后序左子树；中序右子树，后序右子树
    let nodeVal = postorder[postorder.length - 1],
        node = new TreeNode(nodeVal),
        inorderSplitIndex = inorder.indexOf(nodeVal);

    node.left = buildEveryLevel(inorder.slice(0, inorderSplitIndex), postorder.slice(0, inorderSplitIndex))
    node.right = buildEveryLevel(inorder.slice(inorderSplitIndex + 1), postorder.slice(inorderSplitIndex, postorder.length - 1))

    return node
}



/**
 * 递归-官解
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
    let postorderIndex = postorder.length - 1;
    function buildEveryLevel(left, right) {
        if (left > right) return null;

        let nodeVal = postorder[postorderIndex],
            node = new TreeNode(nodeVal),
            inorderIndex = inorder.indexOf(nodeVal)

        postorderIndex--

        node.right = buildEveryLevel(inorderIndex + 1, right)
        node.left = buildEveryLevel(left, inorderIndex - 1)

        return node

    }
    return buildEveryLevel(0, inorder.length - 1)
};


/**
 * map的查找比arr的indexOf方法更快
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
    let postorderIndex = postorder.length - 1,
    inorderMap = new Map();
    inorder.forEach((val,index)=>{
        inorderMap.set(val,index)
    })
    function buildEveryLevel(left, right) {
        if (left > right) return null;

        let nodeVal = postorder[postorderIndex],
            node = new TreeNode(nodeVal),
            inorderIndex = inorderMap.get(nodeVal)

        postorderIndex--

        node.right = buildEveryLevel(inorderIndex + 1, right)
        node.left = buildEveryLevel(left, inorderIndex - 1)

        return node

    }
    return buildEveryLevel(0, inorder.length - 1)
};
